- Sieb des Eratosthenes
- I
Sieb des Eratọsthenes,ein auf Eratosthenes von Kyrene zurückgehender Algorithmus zur Ermittlung aller Primzahlen, die kleiner oder gleich einer vorgegebenen Grenze n sind. Hierzu schreibt man die Zahlen 2 bis n auf und streicht nacheinander die Vielfachen von 2, 3, 5, 7 usw.; dabei braucht man nur bis zu den Vielfachen von zu gehen. Das Sieb des Eratosthenes ist besonders für kleine n von praktischer Bedeutung, da der mit ihm verbundene Rechenaufwand sehr hoch ist.IISieb des Eratosthenes,ein von dem griechischen Philosophen Eratosthenes im dritten vorchristlichen Jahrhundert angegebenes Verfahren, mit dem sich alle Primzahlen berechnen lassen, die kleiner sind als eine vorgegebene natürliche Zahl n. Dazu schreibt man alle Zahlen von 1 bis n auf und streicht die Zahl 1. Im zweiten Schritt betrachtet man die kleinste noch nicht gestrichene und nicht markierte Zahl i. Man markiert sie und streicht alle Vielfachen von i (»Aussieben« der Vielfachen). Dieser Schritt wird so lange wiederholt, bis für die betrachtete kleinste Zahl i gilt: i2 > n. Dann sind alle markierten und die nicht gestrichenen Zahlen die Primzahlen von 1 bis n.Der obige Algorithmus lässt sich in den meisten Programmiersprachen leicht umsetzen und dient daher als beliebtes Beispiel für die Programmierung einer bedingten Schleife.
Universal-Lexikon. 2012.
